import java.util.*;

public class demo {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int T=scanner.nextInt();
        while(T>0) {
            int n=scanner.nextInt();
            long k=scanner.nextInt();//k范围10^13次方需要使用long
            //使用HashMap存储每种职业的士兵数量
            Map<Integer, Long>h=new HashMap<>();
            for (int i = 0; i <n ; i++) {
                int a=scanner.nextInt();
                int b=scanner.nextInt();
                h.put(a,h.getOrDefault(a,0L)+b);
            }
            //将HashMap 中的士兵数量转换为列表
            List<Long> b=new ArrayList<>(h.values());
            long cnt=0;//记录完整纯职业小组数量
            long res=0;//记录选中士兵总数
            //计算可以组成的完整小组数量，并使用每个职业的士兵
            for (int i = 0; i <b.size() ; i++) {
                //计算当前职业可以组成的完整小组数量
                long fullgroups=b.get(i)/3;
                cnt+=fullgroups;
                long used =Math.min(b.get(i),2);//从当前职业中最多使用2名士兵
                b.set(i,b.get(i)-used);//更新剩余士兵数量
                res+=used;//增加选中士兵数量
            }
            if(cnt<k){
                System.out.println(-1);
                continue;
            }
            //统计剩余士兵的数量
            long c1=0,c2=0,c3=0;//剩余单兵c1,双兵c2,三兵c3
            for (long x:b){
                //统计剩余完整小组数量
                c3+=x/3;
                x%=3;//计算剩余士兵的数量
                if(x==1){
                    c1++;//统计剩余单兵
                } else if (x==2) {
                c2++;//统计剩余双兵
                     }
            }
            //先减去一个小组的需求
            k--;
            res++;//选中一个小组的士兵
            //尝试用剩余的完整小组来满足k的需求
            long v=Math.min(k,c3);
            k-=v;//减去已满足的需求
            c3-=v;//更新完整小组的数量
            res+=v*3;//增加选择士兵数量
            //尝试用剩余的双兵小组来满足k的需求
            v=Math.min(k,2);
            k-=v;
            c2-=v;
            res+=v*2;

            v=Math.min(k,c1);
            k-=v;
            c1-=v;
            res+=c1;
            System.out.println(res);
            T--;
        }
    }
}
